//
// Created by fh on 2021/5/28.
//

#include "LinkList.h"

/* 在L中第i个位置之后插入新的数据元素e，L的长度加1：这里头结点要传地址进去，
 * 因为需要修改属性next的值，如果只是传值Node只是传了一份实参的拷贝，
 * 修改了next的值只是修改了形参的值不会影响到实际参数的next */
Status LinkListInsert(Node *headerNode,int i,ElemType e) {
    Node *p = headerNode;
    int j = 1;
    // i-1保证遍历最后p指向要插入的位置的前一个结点
    while (j < i && p != NULL) {
        p = p->next;
        j++;
    }
    if (p == NULL || j > i) {
        return ERROR;
    }
    // 此时p指向第i个位置(算上头结点)
    /* 这里不能用Node createNode = {};这种方式新增节点，因为这样是存在栈帧的，当这个函数调用结束后这个自动变量就会出栈，
       你的指针就可能指向了一块被其他函数栈帧覆盖的区域，后果未可知,用malloc就保证结点是存在堆里，而堆是由程序员自己开辟自己释放的 */
    Node *createNode = (Node *)malloc(sizeof(Node));
    createNode->data = e;
    createNode->next = p->next;
    p->next = createNode;
    return OK;
}

/* 删除L的第i个数据元素，并用e返回其值，L的长度-1 */
Status LinkListDelete(Node *headerNode,int i,ElemType *e) {
    Node *p = headerNode;
    int j = 1;
    // i-1保证遍历最后p指向要插入的位置的前一个结点
    while (j < i && p != NULL) {
        p = p->next;
        j++;
    }
    if (p == NULL || j > i) {
        return ERROR;
    }
    // 此时p指向第i个位置(算上头结点)
//    printf("想要删除第%d个,不算头结点\n",i);
//    printf("此时p指向第%d个位置(算上头结点),data:%d\n",j,p->data);
    Node *q = p->next;
    if (q == NULL) {
        return ERROR;
    }
    p->next = q->next;
//    p->next = p->next->next; // 不能单单用这种方式删而不用中间变量q，因为这样要删除的节点就丢失了，这样就没法free释放了
    *e = q->data;
    free(q);
    q = NULL;
    return OK;
}

/* 用e值修改L的第i个元素数据 */
Status LinkListModify(Node *headerNode,int i,ElemType e) {
    Node *p = headerNode;
    int j = 1;
    // i-1保证遍历最后p指向要插入的位置的前一个结点
    while (j < i && p != NULL) {
        p = p->next;
        j++;
    }
    if (p == NULL || j > i) {
        return ERROR;
    }
    // 此时p指向第i个位置(算上头结点)
    if (p->next == NULL) {
        return ERROR;
    }
    p->next->data = e;
    return OK;
}

/* 用e返回L中第i个数据元素的值 */
Status LinkListGetElem(Node headerNode,int i,ElemType *e) {
    Node *p = &headerNode; // 用指针的方式访问比较方便
    if (i < 1 || p == NULL) {
        return ERROR;
    }
    int j = 1;
    while (j != i && p != NULL) {
        p = p->next;
        j++;
    }
    if (j > i || p == NULL) {
        return ERROR;
    }
    if (p->next == NULL) {
        return ERROR;
    }
    *e = p->next->data;
    return OK;
}

/* 打印单链表 */
Status LinkListDisplay(Node headerNode) {
    // 用指针的方式访问比较方便,用Node类型的话第一个节点headerNode不好跟NULL比较判断空
    Node *p = &headerNode;
//    printf("头部节点地址: %p\n",p);
    printf("遍历结果:");
    while (p != NULL) {
        printf(" %d ",p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}
/* 另一种打印单链表,L指向的Node节点不能修改，如果不设置为const那么有可能在函数里动了L的属性值 */
Status LinkListAnotherDisplay(const Node *L) {
    printf("遍历结果:");
    Node *p = L;
    while (p != NULL) {
        printf(" %d ",p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

/* 随机产生n个元素的值，建立带头结点的单链线性表(头插法) */
Node * LinkListCreateListHead(int n) {
    Node *head = (Node *)malloc(sizeof(Node));
    head->data = 0;
    head->next = NULL;
    Node *p = NULL;
    while (n > 0) {
        Node *create = (Node *)malloc(sizeof(Node));
        create->data = rand() % 100 + 1;
//        create->data = n;
        create->next = p;
        head->next = create;
        p = create;
        n--;
    }
    return head;
}

/* 随机产生n个元素的值，建立带头结点的单链线性表(尾插法) */
Node * LinkListCreateListTail(int n) {
    Node *head = (Node *)malloc(sizeof(Node));
    head->data = 0;
    head->next = NULL;

    Node *p = head;
    for (int i = 0; i < n; ++i) {
        Node *create = (Node *)malloc(sizeof(Node));
        create->data = i+1;
        create->next = NULL;
        p->next = create;
        p = create;
    }
    return head;
}

/* 顺序线性表L已经存在，将它重置为空表 */
Status LinkListClearList(Node **headerNode) {
    Node *p = (*headerNode)->next;
    Node *q = NULL;
    while (p != NULL) {
        // 这里一定要先保存一下p的后继指针，不然下一步free释放的时候就找不到p的后继指针了
        q = p->next;
        free(p);
        p = q;
    }
    // 不加这一行代码的话最后头节点还是指向了第一个节点，但是那个节点已经释放了内存，遍历链表时会出现访问已经释放内存的错误
    (*headerNode)->next = NULL;
    return OK;
}

void InnerTestStructAddress(Node *head) {
    printf("函数里形参地址：%p\n",&head);
    printf("函数里形参值：%p\n",head);
    printf("修改前函数里形式参数指向的内容：data: %d next:%p\n",head->data,head->next);
    Node *q = (Node *) malloc(sizeof(Node));
    head->data = 999;
    head->next = q;
    printf("修改后函数里形式参数指向的内容：data: %d next:%p\n",head->data,head->next);
}

/* 测试demo */
void linkListTestDemo() {

    /*
    {
        printf("--------------------------- 函数结构体参数传值学习 ------------------------\n");
        Node *first = (Node *) malloc(sizeof(Node));
        first->data = 3;
        first->next = NULL;
        printf("实参地址：%p\n",&first);
        printf("实参值：%p\n",first);
        printf("调用函数前实际参数指向的内容：data: %d next:%p\n",first->data,first->next);
        InnerTestStructAddress(first);
        printf("调用函数后实际参数指向的内容：data: %d next:%p\n",first->data,first->next);

    }
    return;
    {
        printf("--------------------------- 链表整表删除 ------------------------\n");
        Node *second = (Node *) malloc(sizeof(Node));
        second->data = 3;
        second->next = NULL;

        Node *first = (Node *) malloc(sizeof(Node));
        first->data = 1;
        first->next = second;

        free(first);
        Node *p = first->next;
        printf("%d\n",p->data);
        printf("%p\n",p->next);

        LinkListAnotherDisplay(first);

    }
    return;
    {
        printf("--------------------------- 链表整表初始化尾插法 ------------------------\n");
        Node *L = LinkListCreateListTail(10);
        Status result = LinkListAnotherDisplay(L);
        printf("LinkListCreateListTail result : %d\n",result);

        result = LinkListClearList(&L);
        printf("LinkListClearList result : %d\n",result);

        result = LinkListAnotherDisplay(L);
        printf("LinkListCreateListTail result : %d\n",result);
    }
    return;
    {
        printf("--------------------------- 链表整表初始化头插法 ------------------------\n");
        Node *L = (30);
        Status result = LinkListAnotherDisplay(L);
        printf(" result : %d\n",result);
    }
    return;
    //*/
    {
        printf("--------------------------- 增 ------------------------\n");
        /*
        Node *head = (Node *)malloc(sizeof(Node));
        head->data = 0;
        head->next = NULL;
        //*/
        // head是头结点，不算链表的第一个结点，打印的时候不用打印的
        Node head = {
                0,
                NULL
        };
        printf("实参地址：%p\n",&head);

        Status result = LinkListInsert(&head,0,1);
        printf("LinkListInsert result: %d\n",result);
        LinkListDisplay(head);

        result = LinkListInsert(&head,1,2);
        printf("LinkListInsert result: %d\n",result);
        LinkListDisplay(head);

        result = LinkListInsert(&head,2,4);
        printf("LinkListInsert result: %d\n",result);
        LinkListDisplay(head);
        //        LinkListDisplay(*head.next);

        result = LinkListInsert(&head,3,5);
        printf("LinkListInsert result: %d\n",result);
        LinkListDisplay(head);

        result = LinkListInsert(&head,3,89);
        printf("LinkListInsert result: %d\n",result);
        LinkListDisplay(head);
        //        LinkListDisplay(*head.next);

        printf("--------------------------- 删 ------------------------\n");
        int a = 0;
        LinkListDelete(&head,2,&a);
        printf("LinkListDelete result: %d\n",result);
        printf("a: %d\n",a);
        LinkListDisplay(head);

        printf("--------------------------- 查 ------------------------\n");
        LinkListGetElem(head,2,&a);
        printf("LinkListGetElem result: %d\n",result);
        printf("a: %d\n",a);
        LinkListDisplay(head);

        printf("--------------------------- 改 ------------------------\n");
        LinkListModify(&head,3,7);
        printf("LinkListModify result: %d\n",result);
        LinkListDisplay(head);
    }
    return;
    {
        printf("--------------------------- 遍历方法1 ------------------------\n");
        Node *head = (Node *)malloc(sizeof(Node));
        head->data = 78;
        head->next = NULL;
        printf("before display : %d\n",head->data);
        LinkListAnotherDisplay(head);
        printf("after display : %d\n",head->data);
        free(head);
        head = NULL;
    }
//    return;
    {
        printf("--------------------------- 遍历方法2 ------------------------\n");
        Node *head = (Node *)malloc(sizeof(Node));
        head->data = 78;
        head->next = NULL;
        printf("head : %p\n",head);
        LinkListDisplay(*head);
        free(head);
        head = NULL;

        Node a = {
                13,
                NULL
        };
        Node anotherHead = {
                3,
                &a
        };
        printf("anotherHead : %p\n",&anotherHead);
        LinkListDisplay(anotherHead);
    }

}


/* 单链表反转 */
void LinkListReverseList(Node *headNode) {
    if (headNode->next == NULL) {
        return; /* 空链表直接返回 */
    }
    if (headNode->next->next == NULL) {
        return; /* 只有一个结点不需要反转 */
    }
    Node *p = headNode->next;
    Node *q = headNode->next->next;
    Node *t = NULL;
    p->next = NULL;

    while (q->next != NULL) {
        t = q->next;
        q->next = p;
        p = q;
        q = t;
    }
    q->next = p;
    headNode->next = q;
}

/* 生成一个带环的链表:这个方法生成的链表不能直接遍历,不然会死循环 */
Node * LinkListCreateLoopList(int n,int index) {
    if (index >= n) {
        return NULL;
    }
    Node *head = (Node *)malloc(sizeof(Node));
    head->data = 0;
    head->next = NULL;
    Node *p = head;
    for (int i = 0; i < n; ++i) {
        Node *create = (Node *)malloc(sizeof(Node));
        create->data = i+1;
        create->next = NULL;
        p->next = create;
        p = create;
    }

    Node *q = head;
    int i = 0;
    while (i < index) {
        q = q->next;
        i++;
    }
    p->next = q;
    return head;
}

/* 单链表中环的检测,有环返回1，无环返回0 */
int LinkListLoopCheckList(Node *headNode) {
    int result = 0;
    if (headNode == NULL || headNode->next == NULL || headNode->next->next == NULL) {
        return result;
    }
    Node *p = headNode->next;
    Node *q = headNode->next;
    while (q != NULL && p != NULL) {
        p = p->next;
        q = q->next->next;
        if (p == q) {
            result = 1;
            break;
        }
    }
    return result;
}

/* 根据给的数组创建单链表 */
Node * LinkListCreateLink(int array[],int length) {
    Node *head = (Node *) malloc(sizeof(Node));
    head->data = 0;
    Node *p = head;
    for (int i = 0; i < length; ++i) {
        Node *create = (Node *) malloc(sizeof(Node));
        create->data = *(array+i);
        create->next = NULL;
        p->next = create;
        p = create;
    }
    return head;
}

/* 链表合并 */
Status LinkListMerge(Node *a,Node *b,Node **c) {
    if (a == NULL && b == NULL) {
        return ERROR;
    }
    if (a == NULL || a->next == NULL) {
        *c = b;
        return OK;
    }
    if (b == NULL || b->next == NULL) {
        *c = a;
        return OK;
    }
    Node *k = a;
    Node *p = a->next;
    Node *q = b->next;

    while (p != NULL && q != NULL) {
        if (p->data < q->data) {
            k->next = p;
            k = p;
            p = p->next;
        } else {
            k->next = q;
            k = q;
            q = q->next;
        }
    }
    if (q == NULL) {
        k->next = p;
    }
    if (p == NULL) {
        k->next = q;
    }
    *c = a;

    return OK;
}

/* 删除链表倒数第n个结点 */
Status LinkListDeleteReciprocalNode(Node *headNode,int n) {
    Node *p = headNode;
    Node *q = headNode;
    int i = 0;
    int length = 0;
    while (p->next != NULL) {
        if (i < n) {
            p = p->next;
            i++;
        } else {
            p = p->next;
            q = q->next;
        }
        length++;
    }
    printf("i:%d\n",i);
    printf("长度:%d\n",length);
    if (n > length) {
        printf("要删除的下标超过链表的长度\n");
        return ERROR;
    }
    if (q != NULL) {
        printf("此时q: %d\n",q->data);
    }
    printf("此时p: %d\n",p->data);
    p = q->next; /* 要删除的结点 */
    q->next = q->next->next;
    free(p);
    p = NULL;
    return OK;
}

/* 求链表的中间结点 */
Status LinkListFindMiddleNode(Node *headNode) {
    if (headNode == NULL || headNode->next == NULL) {
        return ERROR;
    }
    Node *p = headNode->next;
    Node *q = headNode->next;
    while (1) {
        if (p->next == NULL) {
            break;
        } else if (p->next->next == NULL) {
            break;
        }
        p = p->next->next;
        q = q->next;
        if (p == q) {
            return ERROR;
        }
    }
    if (q) {
        printf("q：%d\n",q->data);
    }
    return OK;
}

/* 链表其他常见操作合集测试demo */
void extraLinkTestDemo() {
    {
        Node *l = (6);
        printf("--------------------------- 单链表反转 ------------------------\n");
        LinkListAnotherDisplay(l);
        LinkListReverseList(l);
        LinkListAnotherDisplay(l);

        int result = LinkListLoopCheckList(l);
        printf("是否存在环: %d\n",result);

        free(l);
        l = NULL;
    }

    {
        printf("--------------------------- 单链表中环的检测 ------------------------\n");
        Node *m = LinkListCreateLoopList(10,6);
        int result = LinkListLoopCheckList(m);
        printf("是否存在环: %d\n",result);
        free(m);
        m = NULL;
    }

    {
        printf("--------------------------- 根据数组创建单链表 ------------------------\n");
        int a[] = {1,2,4,6,8,12,24,58,69,89};
        int length = sizeof(a) / sizeof(int);
        Node *n = LinkListCreateLink(a,length);
        LinkListAnotherDisplay(n);
        free(n);
        n = NULL;
    }

    {
        printf("--------------------------- 两个有序的链表合并 ------------------------\n");
        int a[] = {1,2,4,6,8,12,24,58,69,89};
        int length = sizeof(a) / sizeof(int);
        Node *l = LinkListCreateLink(a,length);
        LinkListAnotherDisplay(l);

        int b[] = {1,3,5,15,25,44,50,61,72};
        length = sizeof(b) / sizeof(int);
        Node *ll = LinkListCreateLink(b,length);
        LinkListAnotherDisplay(ll);

        Node *s = NULL;
        LinkListMerge(l,ll,&s);
        LinkListAnotherDisplay(s);

        LinkListAnotherDisplay(l);
        LinkListAnotherDisplay(ll);

        free(l);
        l = NULL;
        free(ll);
        ll = NULL;

    }

    {
        printf("--------------------------- 删除链表倒数第n个结点 ------------------------\n");
        int a[] = {1,2,4,6,8,12,24,58,69,89};
        int length = sizeof(a) / sizeof(int);
        Node *l = LinkListCreateLink(a,length);
        LinkListAnotherDisplay(l);

        LinkListDeleteReciprocalNode(l,9);
        LinkListAnotherDisplay(l);

        free(l);
        l = NULL;
    }

    {
        printf("--------------------------- 求链表的中间结点 ------------------------\n");
        int a[] = {1,2,3,4,5,6,7,8};
        int length = sizeof(a) / sizeof(int);
        Node *l = LinkListCreateLink(a,length);
        LinkListAnotherDisplay(l);

        LinkListFindMiddleNode(l);

        free(l);
        l = NULL;
    }

}